package sit.engreal.leetcode.problems100;
/**
 * <a href="https://leetcode.cn/problems/search-insert-position/">35. 搜索插入位置</a>
 */
public class LeetCode35 {
    public static void main(String[] args) {
        class Solution {
            public int searchInsert(int[] nums, int target) {
                int left = 0;
                int right = nums.length;
                while (left < right) {
                    int i = (left + right) / 2;
                    if (nums[i] < target) {
                        left = i + 1;
                    } else if (nums[i] > target) {
                        right = i;
                    } else {
                        return i;
                    }
                }
                return right;
            }
        }

        final Solution solution = new Solution();
        assert 2 == solution.searchInsert(new int[]{1,3,5,6}, 5);
        assert 1 == solution.searchInsert(new int[]{1,3,5,6}, 2);
        assert 4 == solution.searchInsert(new int[]{1,3,5,6}, 7);
    }
}
